package com.zlk.algorithm.dataStructure.tree.treeDp;

import com.zlk.algorithm.dataStructure.tree.TreeNode;

import java.util.LinkedList;

/**
 * @program: algorithm
 * @ClassName IsCBT
 * @description:是否是完全二叉树
 *   （一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，
 *   如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。）
 * @author: slfang
 * @create: 2024-02-18 20:55
 * @Version 1.0
 **/
public class IsCBT {



    //分析
    // 思路就是按层遍历
    // 原则： 1、 当存在右子树情况下，左子树不存在的直接返回false
    //       2、 当第一次出现左右孩子不双全的情况下，剩下都是叶子节点



    //方法1
    // 1、 当存在右子树情况下，左子树不存在的直接返回false
    // 2、 当第一次出现左右孩子不双全的情况下，剩下都是叶子节点
    public boolean isCbt1(TreeNode head){
        if (head == null) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 是否遇到过左右两个孩子不双全的节点
        boolean leaf = false;
        TreeNode l = null;
        TreeNode r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
                    (leaf && (l != null || r != null)) || (l == null && r != null)

            ) {
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {
                leaf = true;
            }
        }
        return true;
    }

    //方法2 树形dp  todo 看下原来的
    // a、可能性
    // b、信息  左树不是是完全二叉树  右树是不是完全二叉树  合起来是否是完全二叉树
    //   完全二叉树的定义：
    //




}
